﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<string.h>
#include<stdbool.h>
#include<stdio.h>

//int hammingWeight(uint32_t n)
//{
//	int amount = 0;
//	while (n)
//	{
//		amount++;
//		n = n & (n - 1);
//	}
//	return amount;
//}

//bool isUgly(int n)
//{
//	if (n < 0)
//		return false;
//	while (n%2==0||n%3==0||n%5==0)
//	{
//		if (n % 2 == 0)
//			n /= 2;
//		else if (n % 3 == 0)
//			n /= 3;
//		else
//			n /= 5;
//	}
//	if (n == 1)
//		return true;
//	else
//		return false;
//}

//给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），
// 并交换这两个下标所对应的字符。
//如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
//bool areAlmostEqual(char* s1, char* s2)
//{
//	int len = strlen(s1);
//	if (len == 0)
//	{
//		return true;
//	}
//	else
//	{
//		int x=-1, y=-1;
//		int i = 0;
//		for (i = 0; i < len; i++)
//		{
//			if (s1[i] != s2[i])
//			{
//				if (x == -1)
//				{
//					x = i;
//				}
//				else
//				{
//					y = i;
//					break;
//				}
//			}
//		}
//		if (x == -1)
//			return true;
//		if (x != -1 && y == -1)
//			return false;
//		char tmp = s1[x];
//		s1[x] = s1[y];
//		s1[y] = tmp;
//		if (strcmp(s1, s2) == 0)
//			return true;
//	}
//	return false;
//}
//int main()
//{
//	char p1[] = "aa";
//	char p2[] = "ac";
//	areAlmostEqual(p1, p2);
//	return 0;
//}

//输入：nums = [1,2,2,1,1,0]
//输出：[1, 4, 2, 0, 0, 0]
//解释：执行以下操作：
//- i = 0: nums[0] 和 nums[1] 不相等，跳过这步操作。
//- i = 1 : nums[1] 和 nums[2] 相等，nums[1] 的值变成原来的 2 倍，nums[2] 的值变成 0 。数组变成[1, 4, 0, 1, 1, 0] 。
//- i = 2 : nums[2] 和 nums[3] 不相等，所以跳过这步操作。
//- i = 3 : nums[3] 和 nums[4] 相等，nums[3] 的值变成原来的 2 倍，nums[4] 的值变成 0 。数组变成[1, 4, 0, 2, 0, 0] 。
//- i = 4 : nums[4] 和 nums[5] 相等，nums[4] 的值变成原来的 2 倍，nums[5] 的值变成 0 。数组变成[1, 4, 0, 2, 0, 0] 。
//执行完所有操作后，将 0 全部移动到数组末尾，得到结果数组[1, 4, 2, 0, 0, 0] 。
//重写了但没优化
//int* applyOperations(int* nums, int numsSize, int* returnSize)
//{
//	*returnSiz = numsSize;
//	int i = 0;
//	for (i = 0; i < numsSzie - 1; i++)
//	{
//		if (nums[i] == nums[i + 1])
//		{
//			nums[i] *= 2;
//			nums[i + 1] = 0;
//		}
//	}
//	for (i = 0; i < numsSize; i++)
//	{
//		if (nums[i] == 0)
//		{
//			int j = 0;
//			for (j = i + 1; j < numsSize; j++)
//			{
//				if (nums[j] != 0)
//				{
//					int tmp = nums[i];
//					nums[i] = nums[j];
//					nums[j] = tmp;
//				}
//			}
//		}
//	}
//	return nums;
//}

//重写了一遍，还是原来的思路，没有优化
//bool areOccurrencesEqual(char* s)
//{
//	int arr[26] = { 0 };
//	int len = strlen(s);
//	int i = 0;
//	for (i = 0; i < len; i++)
//	{
//		arr[s[i] - 'a']++;
//	}
//	int flag = 0;
//	for (i = 0; i < 26; i++)
//	{
//		if (arr[i] != 0)
//		{
//			if (flag == 0)
//			{
//				flag = arr[i];
//			}
//			else
//			{
//				if (flag != arr[i])
//					return false;
//			}
//		}
//	}
//	return true;
//}

//给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
//对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
//未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
//

int cump(const void*a, const void*b)
{
	return *(int*)a - *(int*)b;
}

int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize)
{
	*returnSize = arr1Size;
	int i = 0;
	int j = 0;
	int n = 0;
	for (i = 0; i < arr2Size; i++)
	{
		for (j = 0; j < arr1Size; j++)
		{
			if (arr1[j] == arr2[i])
			{
				int tmp = arr1[j];
				arr1[j] = arr1[n];
				arr1[n] = tmp;
				n++;
			}
		}
		j = n;
	}
	qsort(arr1 + n, (arr1Size - n), sizeof(int), cump);
	return arr1;
}
int main()
{
	int arr1[] = { 1,3,5,6,7,8,3,2,5,4,};
	int arr2[] = { 1,2,3,4,5 };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	int sz2 = sizeof(arr2) / sizeof(arr2[0]);
	int num = 0;
	relativeSortArray(arr1, sz1, arr2, sz2, &num);
	int i = 0;
	for (i = 0; i < sz1; i++)
	{
		printf("%d ", arr1[i]);
	}
	return 0;
}